Universality of deep convolutional neural networks

Deep learning has been widely applied and brought breakthroughs in speech recognition, computer vision, and many other domains. Deep neural network architectures and computational issues have been well studied in machine learning. But there lacks a theoretical foundation for understanding the approximation or generalization ability of deep learning methods generated by the network architectures such as deep convolutional neural networks. Here we show that a deep convolutional neural network (CNN) is universal, meaning that it can be used to approximate any continuous function to an arbitrary accuracy when the depth of the neural network is large enough. This answers an open question in learning theory. Our quantitative estimate, given tightly in terms of the number of free parameters to be computed, verifies the efficiency of deep CNNs in dealing with large dimensional data. Our study also demonstrates the role of convolutions in deep CNNs.     

Approximation of quantum assemblages

In this paper, we derive a set of projectors on a large Hilbert space which can universally work for approximating quantum assemblages with binary inputs and outputs. The dimension of the Hilbert space depends on the accuracy of the approximation.     

Separation between second price auctions with personalized reserves and the revenue optimal auction

When buyer valuations are drawn IID from a known regular distribution, a second price auction with a symmetric reserve price is the revenue-optimal single-item auction. When this distribution is irregular, we provide the first separation result showing that a second price auction with reserves earns at most 0.778 times the revenue of Myerson’s optimal auction, even when the reserves can be asymmetric. Since the lower bound is 0.745 for i.i.d. buyers, our result is nearly tight.     

Order acceptance and scheduling with machine availability constraints

We consider an order acceptance and scheduling model with machine availability constraints. The manufacturer (machine) is assumed to be available to process orders only within a number of discontinuous time intervals. To capture the real-life behavior of a typical manufacturer who has restrictions of time availability to process orders, our model allows the manufacturer to reject or outsource some of the orders. When an order is rejected or outsourced, an order-dependent cost of penalty will occur. The objective is to minimize the makespan of all accepted orders plus the total penalty of all rejected/outsourced orders. We study the approximability of the model and some of its important special cases.